/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/next-permutation
   @Language: C++
   @Datetime: 16-02-09 08:18
   */

class Solution {
public:
	/**
	 * @param nums: An array of integers
	 * @return: An array of integers that's next permuation
	 */
	/** Tips: next permuation based on the ascending order sort
	 * sketch :
	 * current: 3   7  6  2  5  4  3  1  .
	 *                    |  |     |     |
	 *          find i----+  j     k     +----end
	 * swap i and k :
	 *          3   7  6  3  5  4  2  1  .
	 *                    |  |     |     |
	 *               i----+  j     k     +----end
	 * reverse j to end :
	 *          3   7  6  3  1  2  4  5  .
	 *                    |  |     |     |
	 *          find i----+  j     k     +----end
	 *
	 * step 1 : find the last pair nums[i], nums[j] which are neighbor
	 *          and nums[i] < nums[j]
	 *    now : the range [j,end) is in descending order
	 * step 2 : find the last element k which is not less than i
	 *          because range[j,end) is in descending order, we can 
	 *          search from end to j
	 *    now : nums[i] <= nums[k]
	 * step 3 : swap i and k
	 *    now : the range [j,end) is also in descending order
	 * step 4 : reverse(j,end) and the range [j,end) is in ascending order
	 *    now : done and return
	 *
	 * notice : if step 1 find the i is equal to begin,
	 *          that menas the whole nums is in descending order
	 *          so, reverse nums and return
	 * */
	vector<int> nextPermutation(vector<int> &nums) {
		// Method 1 : using STL algorithm
		// next_permutation(nums.begin(),nums.end());
		// return nums;
		// Method 2 : do it by yourself
		if (nums.size()<2) return nums;
		vector<int>::iterator i, j, k;
		for (i=nums.end()-1; i!=nums.begin();){
			j = i--;    // find last increasing pair (i,i+1)
			if (!(*i < *j)) continue;
			// find last k which not less than i,
			for (k=nums.end(); !(*i < *(--k)););
			iter_swap(i,k);
			// now the range [j,end) is in descending order
			reverse(j,nums.end());
			return nums;
		}
		// current nums is in descending order
		reverse(nums.begin(),nums.end());
		return nums;
	}
};
